
/**
 * @author LKQ
 * @date 2021/12/2 16:56
 * @description 采用动态规划，f(i)代表以第i个数结尾的【连续子数组的最大和】 f(i) = max{f(i-1)+nums[i], nums[i]}
 */
public class Solution1 {
    public static void main(String[] args) {
        Solution1 solution = new Solution1();
        int[] nums = {-2, 1, -3, 4, -1, 2, 1, -5, 4};
        System.out.println(solution.maxSubArray(nums));
    }

    public int maxSubArray(int[] nums) {
        int pre = 0, maxAns = nums[0];
        for (int x: nums) {
            // 用一个整型变量存储这一个数+前一个数和当前数的大小。
            pre = Math.max(pre + x, x);
            // 只要pre大，那么即赋值给maxAns
            maxAns = Math.max(maxAns, pre);
        }
        return maxAns;
    }


}
